﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LeetCodeSolutions
{
    /// <summary>
    /// 509. 斐波那契数
    /// </summary>
    class LeetCode509 : LeetCodeBase
    {
        public override void Execute()
        {
            int input = int.Parse(Console.ReadLine());
            CommonFuntions.Print(Fib(input));
        }

        Dictionary<int, int> fibValues = new Dictionary<int, int>();

        public int Fib(int n)
        {
            if (n == 0 || n == 1) return n;

            int key1 = n - 1;
            int key2 = n - 2;
            CommonFuntions.Print($"计算{n}，存在{key1}:{fibValues.ContainsKey(key1)}，存在{key2}:{fibValues.ContainsKey(key2)}");

            if (!fibValues.ContainsKey(key1))
            {
                fibValues[key1] = Fib(key1);
                CommonFuntions.Print($"存储{key1}:{fibValues[key1]}");
            }
            if (!fibValues.ContainsKey(key2))
            {
                fibValues[key2] = Fib(key2);
                CommonFuntions.Print($"存储{key2}:{fibValues[key2]}");
            }
            int result1 = fibValues[key1];
            int result2 = fibValues[key2];

            return result1 + result2;
        }
    }
}
